class Solution {
    public int findKthLargest(int[] nums, int k) {
        minHeap minHeap = new minHeap(k);
        for (int i = 0; i <k ; i++) {
            minHeap.offer(nums[i]);
        }

        for (int i = k; i <nums.length ; i++) {
            if(nums[i]>minHeap.peek()){
                minHeap.replace(nums[i]);
            }
        }
        return minHeap.peek();
    }
}
class minHeap{
    private int size=0;
    private  int[] arry;

    public minHeap(int capacity) {
        this.arry = new int[capacity];
    }

    public Boolean offer(int offered){
        if(size==arry.length){
            return false;
        }

        up(offered);
        size++;
        return true;
    }
    public int peek(){
        return arry[0];
    }


    public void up(int offered){
        int child=size;
        while (child>0){
            int parent=(child-1)/2;
            if(offered<arry[parent]){
                arry[child]=arry[parent];
            }else {
                break;
            }
            child=parent;
        }
        arry[child]=offered;
    }

    public void replace(int replaced){
        arry[0]=replaced;
        down(0);
    }

    public void down(int parent){
        int left=parent*2+1;
        int right=left+1;
        int max=parent;
        if(left<size&&arry[max]>arry[left]){
            max=left;
        }
        if (right<size&&arry[max]>arry[right]) {
            max=right;
        }
        if(max!=parent){
            swap(max,parent);
            down(max);
        }
    }

    public void swap(int i,int j){
        int tem=arry[i];
        arry[i]=arry[j];
        arry[j]=tem;
    }
}

//runtime:23 ms
//memory:51.8 MB
